package cn.algorithmdemo.search;

public class Demo02 {
    /*
    二分查找 也叫做折半查找
        说明：元素必须是有序的，从小到大，或者从大到小都是可以的。
            如果是无序的，也可以先进行排序。但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，
            所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。

        基本思想：也称为是折半查找，属于有序查找算法。用给定值先与中间结点比较。比较完之后有三种情况：
        相等 说明找到了
        要查找的数据比中间节点小 说明要查找的数字在中间节点左边
        要查找的数据比中间节点大 说明要查找的数字在中间节点右边
    * */
    public static void main(String[] args) {
        //二分查找/折半查找
        //核心：
        //每次排除一半的查找范围

        //需求：定义一个方法利用二分查找，查询某个元素在数组中的索引
        //数据如下：{7, 23, 79, 81, 103, 127, 131, 147}

        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};
        System.out.println(binarySearch(arr, 81));
    }

    private static int binarySearch(int[] arr, int num) {
        //1.定义两个变量记录要查找的范围
        int min = 0;
        int max = arr.length - 1;
        int sum = 0;
        //2.利用循环不断的去找要查找的数据
        while (true){
            sum++;
            System.out.println(sum);
            if (min > max) {
                return -1;
            }
            //3.找到min和max的中间位置
            int mid = (min+max)/2;
            //4.拿着mid指向的元素跟要查找的元素进行比较
            if (arr[mid] == num){
                //4.3 number跟mid指向的元素一样
                //找到了
                return mid;
            }

            if (arr[mid] < num){
                //4.2 number在mid的右边
                //max不变，min = mid + 1;
                min = mid + 1;
            }else{
                //4.1 number在mid的左边
                //min不变，max = mid - 1；
                max = mid - 1;
            }
        }
    }
}
